
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Partition {
public:
	ListNode* partition(ListNode* pHead, int x) {
		if (NULL == pHead || x < 0){
			return NULL;
		}
		//定义两个新链表头节点
		ListNode head1(0), head2(0);
		ListNode* tail1 = &head1;
		ListNode* tail2 = &head2;
		ListNode* cur = pHead;
		while (cur){
			if (cur->val < x){
				tail1->next = cur;
				tail1 = tail1->next;
			}
			else{
				tail2->next = cur;
				tail2 = tail2->next;
			}
			cur = cur->next;
		}
		tail2->next = NULL;
		tail1->next = head2.next;
		return head1.next;
	}

};